/*

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
// dp + 状态压缩
var uniquePathsWithObstacles = function (obstacleGrid) {
    let n = obstacleGrid.length, m = obstacleGrid[0].length;
    let memo = new Array(m).fill(0);

    memo[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            if (obstacleGrid[i][j] == 1) {
                memo[j] = 0;
                continue;
            }
            if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                memo[j] += memo[j - 1];
            }
        }
    }

    return memo[m - 1];
};

// dp 
var uniquePathsWithObstacles = function (obstacleGrid) {
    let n = obstacleGrid.length
    if (!n || obstacleGrid[0][0] === 1) return 0 // 空数组或开始方块就是障碍的情况
    if (n === 1) return Number(!obstacleGrid[0].includes(1)) // 当只有一行的情况

    let m = obstacleGrid[0].length
    let dp = Array.from(new Array(n + 1), _ => new Array(m + 1).fill(0)) // 生成 (m + 1) * (n + 1) 的数组
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (i === 1 && j === 1) {// 使dp[1][1] = 1 , dp[1][1] 对应 obstacleGrid[0][0]
                dp[i][j] = 1
            } else if (obstacleGrid[i - 1][j - 1] != 1) {// 当不是障碍物时 dp[当前] = dp[上] + dp[左]
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            } else { // 当碰到障碍物 说明此路不通  dp[i][j] = 0
                dp[i][j] = 0
            }
        }
    }
    return dp[n][m]
};